package com.example.leetcode.tree;

import com.example.leetcode.tree.common.TreeNode;
import com.example.leetcode.tree.common.TreeUtils;

public class leetcode124 {
    public static void main(String[] args) {
        Integer[] nums = {-10, 9, 20, null, null, 15, 7};
        TreeNode root = TreeUtils.generateLeetcodeTree(nums);

        Solution solution = new Solution();

        int sum = solution.maxPathSum(root);
        System.out.println(sum);
    }

    static class Solution {
        public int maxPathSum = Integer.MIN_VALUE;

        public int maxPathSum(TreeNode root) {
            dfs(root);
            return maxPathSum;
        }

        public int dfs(TreeNode root) {
            if (root == null) {
                return 0;
            }

            int left = Math.max(dfs(root.left), 0);
            int right = Math.max(dfs(root.right), 0);

            // 拐点时计算最大值
            int curMax = left + right + root.val;

            maxPathSum = Math.max(maxPathSum, curMax);

            // 往上传递
            return Math.max(left, right) + root.val;
        }
    }
}
